package offer_test_60;

import struct.BinaryTreeNode;
import struct.LinkedNode;
import struct.MyStack;

//求树中2节点的最小公共祖先，仅有根指向左右子树的指针。
public class ten_CommonNodeInTree {
	public static void main(String[] args) {
		BinaryTreeNode root1 = new BinaryTreeNode();
		BinaryTreeNode node1 = new BinaryTreeNode();
		BinaryTreeNode node2 = new BinaryTreeNode();
		BinaryTreeNode node3 = new BinaryTreeNode();
		BinaryTreeNode node4 = new BinaryTreeNode();
		root1.leftNode = node1;
		root1.rightNode = node2;
		node1.leftNode = node3;
		node1.rightNode = node4;
		root1.value = 10;
		node1.value = 5;
		node2.value = 12;
		node3.value = 4;
		node4.value = 7;
//		MyStack stack = new MyStack(100);
//		searchNode(root1, node4, stack);
//		while (!stack.isEmpty()) {
//			BinaryTreeNode temp = (BinaryTreeNode) stack.pop();
//			System.out.print(temp.value + " ");
//		}
		System.out.println(getCommonNode(root1, node3, node4).value);
	}

	public static boolean searchNode(BinaryTreeNode node, BinaryTreeNode aim,
			MyStack s) {
		boolean judge = false;
		if (node == null) {
			return false;
		}
		if (node.value == aim.value) {
			s.push(node);
			return true;
		}
		s.push(node);
		if (!judge && node.leftNode != null) {
			judge = searchNode(node.leftNode, aim, s);
		}
		if (!judge && node.rightNode != null) {
			judge = searchNode(node.rightNode, aim, s);
		}
		if (!judge)
			s.pop();
		return judge;
	}

	public static BinaryTreeNode getCommonNode(BinaryTreeNode node,
			BinaryTreeNode one, BinaryTreeNode two) {
		MyStack onestack = new MyStack(100);
		MyStack twostack = new MyStack(100);
		searchNode(node, one, onestack);
		searchNode(node, two, twostack);
		BinaryTreeNode tempone = new BinaryTreeNode();
		BinaryTreeNode temptwo = new BinaryTreeNode();
		BinaryTreeNode commonNode = null;
		boolean judge = false;
		while (!onestack.isEmpty() && !twostack.isEmpty()) {
			tempone = (BinaryTreeNode) onestack.pop();
			temptwo = (BinaryTreeNode) twostack.pop();
			if (tempone.value == temptwo.value) {
				commonNode = tempone;
				break;
			}
		}
//		if (judge) {
			return commonNode;
//		}
	}
}
